#include <ctime>
#include <iostream>

using namespace std;
clock_t start;

long iter_fibo(long n);

long tail_recur_fibo(long n, long ret1, long ret2);

int main() {
  long n = 50000;
  const long max_iter = 1000;
  start = clock();
  for (long i = 0; i < max_iter; i++) {
    iter_fibo(n);
  }
  clock_t end = clock();
  double endtime = (double)(end - start) / CLOCKS_PER_SEC;
  cout << "total time(iter_fibo):" << endtime << endl;

  start = clock();
  for (long i = 0; i < max_iter; i++) {
    tail_recur_fibo(n, 1, 1);
  }
  end = clock();
  endtime = (double)(end - start) / CLOCKS_PER_SEC;
  cout << "total time(tail_recur_fibo):" << endtime << endl;
  return 0;
}

long iter_fibo(long n) {
  if (n == 1 || n == 2) {
    return 1;
  }
  long a = 1;
  long b = 1;
  for (long i = 2; i < n; i++) {
    long sum = a + b;
    a = b;
    b = sum;
  }
  return b;
}

long tail_recur_fibo(long n, long a, long b) {
  if (n == 1) {
    return a;
  } else {
    long sum = a + b;
    a = b;
    b = sum;
    return tail_recur_fibo(n - 1, a, b);
  }
}
